Error correction decoding techniques are increasingly being applied to digital communication links to enable significant performance improvements. Those techniques enable, for fixed transmit (or receive) power levels and for allowable bit error probabilities, the transfer of more information per unit time. Several widely employed encoding techniques are categorized as block and convolutional. Block codes (sometimes referred to as algebraic codes) involve the assignment of certain structured blocks of bits to each possible group of information bits. They are highly structured and decoding algorithms generally either exploit code properties that result from the structure or apply probablistic information obtained from the received signal.
Convolutional codes are generally conceded to be operationally better than block codes. To convolutionally encode a digital data stream, a code word of length L (called the constraint length) is employed as a mask. The one bits of the data stream that appear through the mask are Exclusive OR'd to obtain a parity bit from the L length of data bits. The bit stream is then moved by one bit position with respect to the mask, and the process is repeated. This results in the generation of another parity bit which includes information from the new L data bits.
If two different code words are used as masks, then two bits of parity information result for every data bit. The ratio of the number of original data bits to the number of replacement parity bits is called the coding rate. Thus, where one data bit is replaced by two parity bits, the coding rate is one half.
Referring to FIG. 1, a circuit for producing a one-half rate convolutional code is shown and includes shift register 10 which is L positions long, where L equals the length of the code word. Shift register 10 is a serial shift register which receives, in a clocked manner, an input binary digital data stream via input line 12. For this description, it will be assumed that two, 3 bit code words are employed as masks to achieve the convolutional encoding of the data stream. It is to be understood, that three bit code words are merely used for ease of explanation and that, preferably, much longer length code words would be used, as they enable substantially increased error correction capabilities. Furthermore, while only a pair of code words is shown, additional code words may be employed to provide a higher redundancy rate of parity bit transmission.
Code word C1=011 and code word C2=111. Those code words are used as "masks", with each one bit therein indicating that the value present in the corresponding bit position in shift register 10 is fed to an Exclusive OR circuit. Thus, Exclusive OR circuit 14 has applied thereto only data bits appearing in the second and third stages of shift register 10 (per code word C1). Exclusive OR circuit 16 receives inputs from all three stages of shift register 10 and implements code word C2=111. As is well known, Exclusive OR circuits 14 and 16 will only provide "high" outputs when their inputs reflect an odd number of one bits on their input lines. Thus, for each three data bits in shift register 10, Exclusive OR circuit 14 provides an output P1 to multiplexer 18 which is indicative of the data states of the second and third stages of shift register 10. Exclusive OR 16, on the other hand, for each set of bits in shift register 10, provides an output P2 to multiplexer 18 which is indicative of the data states in all three stages. Multiplexer 18 then commutates P1 and P2 onto output line 20 for transmission. As each succeeding bit is fed into shift register 10 and a bit exits therefrom, two new values of P1 and P2 are generated and emplaced on output line 20.
Thus, as each new bit is shifted into the L bit long shift register, there results a pair of parity bits. The existing contents of the register (except for the oldest bit), determines which of four possible values will result from the shifting in of either a Zero or One data bit. Thus, each new data bit affects the current parity pair output and the next L-1 pairs as well.
A decoding technique for analyzing convolutional codes was proposed by A.J. Viterbi. The Viterbi technique is described in "Convolutional Codes and Their Performance in Communications Systems", A.J. Viterbi, IEEE Transactions on Communications Technology, Volume Com-19, No. 5, October 1971, pages 751-772. The Viterbi decoding process requires the continuous tracking of received parity bits through all possible changes in state.
Viterbi's technique can be understood by referring to FIG. 2 which shows the relationships between original data states, new data states, and the possible parity codes P1, P2 which can be generated therefrom. For example, assume an original data state in the encoding shift register of 01. The next bit entering the encoding shift register must be either a 1 or a 0. If the bit is a 1, the resulting data state in the shift register is 11. This results in a P1, P2 parity output of 00. On the other hand, if a 0 enters the encoding shift register, the resulting data state is 10 and the P1, P2 parity state is 11.
However, if the aforementioned state change results in an incorrect parity pair being generated (e.g. 01 or 10), it is known that one or more parity bits are in error.
FIG. 2 thus shows the various possible parity code pairs which can result when an original data state traverses to a new data state by the receipt of a new 0 or 1 bit. In a Viterbi decoding system, an original data state is determined from the analysis of an initial pair of P1, P2 parity bits, and a subsequent data state is determined by the analysis of the next set of P1, P2 parity bits. If the subsequent pair gives rise to an impossible new data state, one or both of the parity bits must be in error. Thus, assuming the initial data state was 10, and the decoding circuitry finds that the subsequent parity code is 11, then it is known that a parity bit is in error since, as FIG. 2 shows, no transition from state 10 can result in a 11 parity pair.
The Viterbi decoding scheme requires that a record be kept of each change of a parity bit to correct an incorrect parity and create an allowed data state transition. This requires that 2.sup.(L-1) states must be continuously tracked. With an L length of 3, this is not a serious problem; however, as L approaches 5,6 or 7, the computing power required to accomplish the continuous tracking increases exponentially.
The Viterbi decoding technique finishes its decoding by selecting the state track with the smallest number of required parity bit changes and designates as acceptable, the data bits associated with that track. This is schematically indicated in FIG. 3 wherein each of the two bit data states are continuously tracked and their subsequent P1, P2 parity bits are also tracked (with X indicating that a subsequent P1, P2 parity pair cannot follow the preceding data state). It is to be noted that the data state track for 10 turns out to be the longest track and is the one selected by the Viterbi decoding system.
It is an object of the present invention to provide a convolutional decoding method and apparatus which is simple in its execution and economic in its implementation.
It is a further object of this invention to provide a convolutional decoding method and system which enables the use of code words longer than heretofore possible.
It is another object of this invention to provide a convolutional decoding system and method which is rapid in its execution and requires no state tracking.
It is a still further object of this invention to provide a convolutional decoding system and method wherein error detection is independent of the data.
It is still another object of this invention to provide a convolutional decoding system and method wherein error correction is readily performed.